package leetcode_400;

import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

/**
 *@author 周杨
 *RemoveInvalidParentheses_301 把表达式校正  
 *describe:用回溯法 并缩小回溯区域 AC 58%
 *2018年6月29日 下午3:31:57
 */
public class RemoveInvalidParentheses_301 {

	public static void main(String[] args) {
		String s="ab";
		System.out.println(s.substring(0,0));

	}
	
	public List<String> removeInvalidParentheses1(String s) {
	    int rmL = 0, rmR = 0;
	    for (int i = 0; i < s.length(); i++) {//缩小dfs的区域  rmR是栈内没有(却遇到)的下标  rml是
	        if (s.charAt(i) == '(') {
	            rmL++;
	        } else if (s.charAt(i) == ')') {
	            if (rmL != 0) {
	                rmL--;
	            } else {
	                rmR++;
	            }
	        }
	    }
	    Set<String> res = new HashSet<>();
	    dfs(s, 0, res, new StringBuilder(), rmL, rmR, 0);
	    return new ArrayList<String>(res);
	}
	
	public void dfs(String s, int i, Set<String> res, StringBuilder sb, int rmL, int rmR, int open) {
	    if (rmL < 0 || rmR < 0 || open < 0) {
	        return;
	    }
	    if (i == s.length()) {
	        if (rmL == 0 && rmR == 0 && open == 0) {//是合法括号表达式
	            res.add(sb.toString());
	        }        
	        return;
	    }

	    char c = s.charAt(i); 
	    int len = sb.length();

	    if (c == '(') {
	        dfs(s, i + 1, res, sb, rmL - 1, rmR, open);		    // not use (
	    	dfs(s, i + 1, res, sb.append(c), rmL, rmR, open + 1);       // use (

	    } else if (c == ')') {
	        dfs(s, i + 1, res, sb, rmL, rmR - 1, open);	            // not use  )
	    	dfs(s, i + 1, res, sb.append(c), rmL, rmR, open - 1);  	    // use )

	    } else {
	        dfs(s, i + 1, res, sb.append(c), rmL, rmR, open);	
	    }

	    sb.setLength(len); //回退
	}
	
	public List<String> removeInvalidParentheses(String s) {
		List<String> res=new ArrayList<String>();
        for(int i=0;i<s.length();++i) {
        	char now=s.charAt(i);
        	if(now=='('||now==')') {
        		String str=s.substring(0,i)+s.substring(i+1);
        		if(help(str)) {
        			if(!res.contains(str))
        				res.add(str);
        		}
        	}
        }
        return res;
    }
	
	public boolean help(String s) {
		int index=0,count=0;
		while(index<s.length()) {
			char now=s.charAt(index);
			if(now=='(')
				++count;
			else if(now==')')
				if(count==0)
					return false;
				else
					--count;
			++index;
		}
		return count==0?true:false;
	}

}
